﻿//给你一个字符串 s，找到 s 中最长的回文子串。
//
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
//
//输入：s = "cbbd"
//输出："bb"
//
//提示：
//	1 <= s.length <= 1000
//	s 仅由数字和英文字母组成

class Solution {
public:
    string longestPalindrome(string s) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        int len = 1, begin = 0; // 标记最⻓⼦串的起始位置和⻓度
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s[i] == s[j])
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                if (dp[i][j] && j - i + 1 > len) // 找出⼦串中最⻓的回⽂⼦串
                    len = j - i + 1, begin = i;
            }
        }
        return s.substr(begin, len);
    }
};
